package _动态规划系列._股票买卖问题;

/**
 * @author: 吕庆龙
 * @date: 2020/3/31 11:35
 * <p>
 * 1.dp数组定义
 * dp[n - 1][K][0]=dp[i][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润
 * <p>
 * 2.状态转移
 * dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1] + price[i])   状态转移就是做选择的过程
 * dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0] - price[i])
 * <p>
 * 3.base case
 * dp[-1][k][0]=0       //第0天，无法交易所以利润为0
 * dp[-1][k][1]=负无穷   //第0天，不可能持有股票，用负无穷代表不可能
 * dp[i][0][0]=0       //最多允许交易0次，那么利润肯定为0
 * dp[i][0][1]=负无穷   //最多允许交易0次，那么就不可能持有股票。所以为不可能
 */
public class Summary_0123 {

    public int maxProfit(int[] prices) {
        if (prices.length <= 1)
            return 0;
        int maxK = 2, n = prices.length;
        int[][][] dp = new int[n][maxK + 1][2];

        for (int i = 0; i < n; i++) {
            for (int k = maxK; k >= 1; k--) {
                if (i - 1 == -1) {
                    //Math.max(dp[-1][k][0], dp[-1][k][1] + prices[i])
                    dp[0][k][0] = 0;
                    //Math.max(dp[-1][k][1], dp[-1][k - 1][0] - prices[i])
                    dp[0][k][1] = -prices[0];
                    continue;

                }

                //状态转移，为什么上面是k,下面是k-1。因为最大交易次数K，其实就可以理解为买入。
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }
        return dp[n - 1][maxK][0];
    }
}
/**
 * 记录一个问题
 * 为什么不能下面这种方式来写
 * dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k-1][1] + prices[i]);
 * dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i]);
 *
 * 上面是把交易次数K理解为买入，所以是 { dp[i - 1][k - 1][0] - prices[i] }
 * 如果把交易次数理解为售出那么就可能发生  当k=1时 dp[i-1][0][1]。而这种情况是不可能的，也就是
 * 不能理解为售出。因为必须要先买才能售出。如果把交易理解为售出，就可能发生没有买就持有股票的情况。
 */
